package com.lfg.leetcode.leetcode100;


public class No164maximumGap {

    public static void main(String[] args) {
        int ret = maximumGap(new int[]{10});
        System.out.println(ret);
    }

    public static int maximumGap(int[] nums) {

        if (nums.length < 2) {
            return 0;
        }

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i : nums) {
            min = Math.min(min, i);
            max = Math.max(max, i);
        }
        int avg = (max - min) / nums.length + 1;
        int size = (max - min) / avg + 1;

        Integer[] minArray = new Integer[size];
        Integer[] maxArray = new Integer[size];

        for (int i : nums) {
            int idx = (i - min) / avg;
            if (minArray[idx] == null) {
                minArray[idx] = i;
            } else {
                minArray[idx] = Math.min(i, minArray[idx]);
            }

            if (maxArray[idx] == null) {
                maxArray[idx] = i;
            } else {
                maxArray[idx] = Math.max(i, maxArray[idx]);
            }
        }

        int index = 0;
        int ret = 0;
        int lastMax = 0;

        for (; index < size; index++) {
            if (minArray[index] == null) {
                continue;
            }
            lastMax = maxArray[index];
            break;
        }
        for (; index < size; index++) {
            if (minArray[index] == null) {
                continue;
            }
            ret = Math.max(ret, minArray[index] - lastMax);
            lastMax = maxArray[index];
        }
        return ret;
    }


}
